﻿// 2521. 数组乘积中的不同质因数数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array/description/

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

注意：

质数 是指大于 1 且仅能被 1 及自身整除的数字。
如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。


示例 1：

输入：nums = [2,4,3,7,10,6]
输出：4
解释：
nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。
共有 4 个不同的质因数，所以返回 4 。
示例 2：

输入：nums = [2,4,8,16]
输出：1
解释：
nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 210 。
共有 1 个不同的质因数，所以返回 1 。


提示：

1 <= nums.length <= 104
2 <= nums[i] <= 1000
*/

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_map<int, int> mm;

        for (int i = 0; i < nums.size(); i++) {
            int res = nums[i];
            for (int i = 2; i <= res / i; i++) {
                while (res % i == 0) {
                    res /= i;
                    mm[i]++;
                }
            }

            if (res > 1) { mm[res]++; }
        }

       

        return mm.size();
    }
};

//2,4,3,7,10,6

int main()
{
    Solution s;
    vector<int> v{ 2,4,3,7,10,6 };
    s.distinctPrimeFactors(v);
}
 